package 蓝桥杯.算法板子.数学;

import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;

/**
 * @Title: 快速幂
 * @Author 贾金博
 * @Package 蓝桥杯.算法板子.数学
 * @Date 2024/4/12 19:21
 * @description:
 */
public class 快速幂 {
    public static  FastReader sc = new FastReader();
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) {
        Long n = sc.nextLong();
        while(n -- != 0) {
//            String a, b, c;
//            a = sc.next();
//            b = sc.next();
//            c = sc.next();
//            out.print(new BigInteger(a).modPow(new BigInteger(b), new BigInteger(c)) + "\n");
            Long a, b, c;
            a = sc.nextLong();
            b = sc.nextLong();
            c = sc.nextLong();
            out.println(ksm(a, b, c));
        }
        out.flush();
    }

    public static Long ksm(Long a, Long b, Long c) {
        Long ret = 1l;
        while(b != 0) {
            if((b & 1) == 1) {
                ret = ret * a % c;
            }
            a = a * a % c;
            b >>= 1;
        }
        return ret;
    }
}

//快读的模板
//class FastReader{
//    StringTokenizer st;
//    BufferedReader br;
//    public FastReader(){
//        br=new BufferedReader(new InputStreamReader(System.in));
//    }
//
//    String next(){
//        while (st==null||!st.hasMoreElements()){
//            try {
//                st=new StringTokenizer(br.readLine());
//            }catch (IOException e){
//                e.printStackTrace();
//            }
//        }
//        return st.nextToken();
//    }
//    int nextInt() {
//        return Integer.parseInt(next());
//    }
//
//    long nextLong() {
//        return Long.parseLong(next());
//    }
//    double nextDouble() {
//        return Double.parseDouble(next());
//    }
//    String nextLine() {
//        String str = "";
//        try {
//            str = br.readLine();
//        } catch (IOException e) {
//            e.printStackTrace();
//        }
//        return str;
//    }
//}
